package com.codermn.先序中序重构二叉树;

import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.Map;

/**
 * @author jxau_scf
 * @date 2021/9/7 - 17:38
 */
public class Solution {
    private int[] preorder;
    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder){
        this.preorder = preorder;
        for (int i = 0;i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }

    private TreeNode recur(int root, int left, int right) {
        if (left > right){
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[root]);
        int idx = map.get(preorder[root]);
        treeNode.left = recur(root + 1, 0, idx - 1);
        treeNode.right = recur(root + (idx - left) + 1, idx + 1, right);
        return treeNode;
    }

    class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
}

